#二叉树

# BinaryTree()创建一个二叉树实例。
# getLeftChild()返回当前节点的左子节点所对应的二叉树。
# getRightChild()返回当前节点的右子节点所对应的二叉树。
# setRootVal(val)在当前节点中存储参数val中的对象。
# getRootVal()返回当前节点存储的对象。
# insertLeft(val)新建一棵二叉树，并将其作为当前节点的左子节点。
# insertRight(val)新建一棵二叉树，并将其作为当前节点的右子节点。

#二叉树的创建有两种方式，第一种称作“列表之列表”，第二种称作“节点与引用”。



#翻转二叉树

#递归法（前序遍历）
def invertTree(tree):
    if not tree:
        return None
    tree.left, tree.right = tree.right, tree.left #中
    invertTree(tree.left) #左
    invertTree(tree.right) #右
    return tree

#迭代法（前序遍历）
def invertTree(tree):
    if not tree:
        return tree
    stack = []
    stack.append(tree)
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left #中
        if node.right:
            stack.append(node.right) #右
        if node.left:
            stack.append(node.left) #左
    return tree

#迭代法（层序遍历）
def invertTree(tree):
    if tree:
        stack.append(tree)
    while stack:
        size = len(stack)
        for i in range(size):
            node = stack.pop(0)
            node.left, node.right = node.right, node.left #中
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
    return tree

#二叉树求和

#递归法（中序遍历）
def addTrees(root1, root2):
        if not root1: 
            return root2
        if not root2: 
            return root1
        root1.val += root2.val # 中
        root1.left = addTrees(root1.left, root2.left) #左
        root1.right = addTrees(root1.right, root2.right) # 右
        return root1

#迭代法（层序遍历）
def addTrees(root1, root2):
        if not root1: 
            return root2
        if not root2: 
            return root1
        stack = [root1,root2]
        while stack: 
            node1 = stack.pop(0)
            node2 = stack.pop(0)
            if node1.left and node2.left: 
                stack.append(node1.left)
                stack.append(node2.left)
            if node1.right and node2.right: 
                stack.append(node1.right)
                stack.append(node2.right)
            node1.val += node2.val
            if not node1.left and node2.left: 
                node1.left = node2.left
            if not node1.right and node2.right: 
                node1.right = node2.right
        return root1

#数组转二叉树
def list2tree(lst):
    root=None
    if lst:
        mid=len(lst)//2
        root = BinaryTree(lst[mid])
        root.left = list2tree(lst[:mid])
        root.right = list2tree(lst[mid+1:])
    return root

#二叉树高度

#递归法
def getdepth(node):
    if not node:
        return 0
    leftdepth = getdepth(node.left) #左
    rightdepth = getdepth(node.right) #右
    depth = 1 + max(leftdepth, rightdepth) #中
    return depth

#迭代法
def getdepth(tree):
    if not tree:
        return 0
    depth = 0 #记录深度
    stack = [tree]
    while stack:
        size = len(stack)
        depth += 1
        for i in range(size):
            node = stack.pop(0)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
    return depth

#最小深度

#递归法
def minDepth(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    min_depth = float('inf')
    if root.left:
        min_depth = min(minDepth(root.left), min_depth) # 获得左子树的最小高度
    if root.right:
        min_depth = min(minDepth(root.right), min_depth) # 获得右子树的最小高度
    return min_depth + 1

#迭代法
def minDepth(root):
    if not root:
        return 0
    stack = [root]
    res = 1
    while stack:
        for _ in range(len(stack)):
            node = stack.popleft()
            if not node.left and not node.right:
                return res
            if node.left is not None:
                stack.append(node.left)
            if node.right is not None:
                stack.append(node.right)
        res += 1
    return res

#完全二叉树节点个数

#递归法
def getNodesNum(tree):
    if not tree:
        return 0
    leftNum = getNodesNum(tree.left) #左
    rightNum = getNodesNum(tree.right) #右
    treeNum = leftNum + rightNum + 1 #中
    return treeNum

#迭代法
def getNodesNum(tree):
    if not tree:
        return 0
    result = 0
    stack = [tree]
    while stack:
        size = len(stack)
        for i in range(size):
            node = stack.pop(0)
            result += 1 #记录节点数量
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
    return result

#最近公共祖先

#递归法
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right: return root
    if left: return left
    return right